package com.sourcetrip.my;


import com.sourcetrip.my.modle.AVLTreeNode;
import com.sourcetrip.my.modle.TreeNode;

import java.util.Comparator;

/**
 * @author: ZhouBert
 * @date: 2020/12/16
 * @description: AVL 树(V0 版本，以后可能还可以进行优化！)
 * 知识点：
 * AVL-Tree 是一棵自平衡二叉搜索树。
 * 自平衡的原理在于：AVL-Tree 多了一个“平衡因子”（left.height - right.height）的概念，当 |平衡因子| > 1 时，AVL-Tree 不平衡。此时需要进行“旋转”处理！
 * 设计：
 * 1.由于继承了 BinarySearchTree ，所以需要给 BinarySearchTree 新建几个钩子方法:afterAdd() + afterRemove(),设置在每次 添加/删除 节点后的修复。
 * 2.抽象出 createNode() 方法，供子类实现；
 * --
 * 难点：
 * 1.add() 时的旋转！
 * 2.remove() 时的处理！
 */
public class AVLTreeV0<E> extends BinarySearchTree<E> {

	//region	constructor
	public AVLTreeV0(Comparator<E> comparator) {
		super(comparator);
	}

	public AVLTreeV0() {
	}
	//endregion


	/**
	 * 创建节点
	 *
	 * @param element 添加的元素
	 * @param parent  添加的节点的父节点
	 * @return
	 */
	@Override
	protected TreeNode<E> createNode(E element, TreeNode<E> parent) {
		AVLTreeNode<E> node = new AVLTreeNode<>(element, parent);
		node.height = 1;
		return node;
	}

	/**
	 * 首先理解旋转：旋转是为了让 长的一端上去一个位置，同时短的一端下来一个位置。
	 * 既然旋转能做到这个事情后，那么针对失衡的节点，只需要旋转一次即可！
	 * 分析：
	 * 当节点添加以后，可能失衡的节点：爷爷节点，祖先节点...
	 * 只要找到最近的失衡的节点，进行一次旋转即可。
	 * --
	 * 难点：
	 * 1.寻找失衡的祖先节点；
	 *
	 * @param node 添加的节点
	 */
	@Override
	protected void afterAdd(TreeNode<E> node) {
		AVLTreeNode<E> cur = (AVLTreeNode<E>) node;
		AVLTreeNode<E> parent = getParentNode(node);
		if (parent == null) {
			return;
		}
		parent.resetHeight();
		AVLTreeNode<E> grand = getParentNode(parent);
		if (grand == null) {
			return;
		}
		grand.resetHeight();
		//找到不平衡的点
		while (grand.isBalance()) {
			cur = parent;
			parent = grand;
			grand = getParentNode(grand);
			if (grand == null) {
				break;
			} else {
				grand.resetHeight();
			}
		}
		if (grand == null) {
			//如果一直平衡，找不到非平衡节点
			return;
		}
		//此时找到了非平衡节点
		if (parent.isLeftChild()) {
			//L
			if (node.isLeftChild()) {
				//L:LL - 将 g 右旋
				rotateRight(grand);
			} else {
				//R:LR - 将 p 左旋；将 g 右旋
				rotateLeft(parent);
				rotateRight(grand);
			}
		} else {
			//R
			if (node.isLeftChild()) {
				//L:RL - 将 p 右旋；将 g 左旋
				rotateRight(parent);
				rotateLeft(grand);
			} else {
				//R:RR - 将 g 左旋
				rotateLeft(grand);
			}
		}
	}

	/**
	 * 移除节点之后的修复
	 * 分析：
	 * 如果删除之后造成AVL-Tree 失衡，那只能父节点失衡！
	 * 因为：删除节点会让子树的高度减少，那么只能影响父节点的平衡因子，让少的子树 -1 ，造成失衡，只有这种可能。
	 * 那么此时调整父节点即可。
	 * 但是此时通过旋转必然会让父节点的高度 -1，此时有可能会造成爷节点失衡；
	 * 经过爷节点的调整，以此类推，可能直至根节点失衡。所以，最差有 O(log height) 的调整
	 *
	 * @param node
	 */
	@Override
	protected void afterRemove(TreeNode<E> node) {
		//由于删除节点保持了对 parent node 的引用
		AVLTreeNode<E> parentNode = getParentNode(node);

//		AVLTreeNode<E> leftNode = null;
//		AVLTreeNode<E> rightNode = null;
//		int leftHeight = 0;
//		int rightHeight = 0;
		AVLTreeNode<E> prev = null;
		//这个写法会进行每次 parentNode reset，可以优化一下：当该节点是 高的子树时才继续循环，否则不进行！
		while (parentNode != null) {
			//由于删除的是叶子节点，当父节点的度为1 变成 0 时，需要进行 resetHeight
			//由于之前已经是调整过的节点，所以需要进行高度的调整
			parentNode.resetHeight();
			prev = getParentNode(parentNode);
			if (!parentNode.isBalance()) {
				//此时 parentNode 处于失衡
				// 由于 child 和 grand child 都需要判断子树的高度，所以将左右子树高度查的逻辑放在 Node 里
//			leftNode = (AVLTreeNode<E>) parentNode.left;
//			rightNode = (AVLTreeNode<E>) parentNode.right;
//			leftHeight = leftNode == null ? 0 : leftNode.height;
//			rightHeight = rightNode == null ? 0 :rightNode.height;

				//这里的旋转其实 和 add() 时进行旋转是一样的。不然用下面这个旋转后还是失衡的！
//				if (!parentNode.isLeftHigher()) {
//					rotateLeft(parentNode);
//				} else {
//					rotateRight(parentNode);
//				}

				AVLTreeNode<E> child = null;
				//进行旋转
				if (parentNode.isLeftHigher()) {
					//L
					child = (AVLTreeNode<E>) parentNode.left;
					if (child.isLeftHigher()){
						//LL
						rotateRight(parentNode);
					}else {
						//LR
						rotateLeft(child);
						rotateRight(parentNode);
					}
				}else {
					//R
					child = (AVLTreeNode<E>) parentNode.right;
					if (child.isLeftHigher()){
						//RL
						rotateRight(child);
						rotateLeft(parentNode);
					}else {
						//RR
						rotateLeft(parentNode);
					}
				}

			}

			parentNode = prev;
		}

	}
//region	private methods

	/**
	 * 获取父节点
	 *
	 * @param node
	 * @return
	 */
	private AVLTreeNode<E> getParentNode(TreeNode<E> node) {
		AVLTreeNode<E> parent = (AVLTreeNode<E>) node.parent;
		return parent;
	}

	/**
	 * 将 grand 节点 左旋
	 * 假设处于：RR
	 *
	 * @param grand
	 */
	public void rotateLeft(AVLTreeNode<E> grand) {
		//拿到 parent 节点的引用
		AVLTreeNode<E> parent = (AVLTreeNode<E>) grand.right;
		//拿到 需要修复的 child 节点(可能为 null)
		AVLTreeNode<E> child = (AVLTreeNode<E>) parent.left;
		//拿到 prev 节点（可能为 null）
		AVLTreeNode<E> prev = (AVLTreeNode<E>) grand.parent;

		parent.left = grand;
		grand.right = child;
		rotateCommon(prev, grand, parent, child);
	}


	/**
	 * 将 grand 节点 右旋
	 * 假设处于：LL
	 *
	 * @param grand
	 */
	public void rotateRight(AVLTreeNode<E> grand) {
		AVLTreeNode<E> parent = (AVLTreeNode<E>) grand.left;
		//拿到 需要修复的 child 节点(可能为 null)
		AVLTreeNode<E> child = (AVLTreeNode<E>) parent.right;
		//拿到 prev 节点（可能为 null）
		AVLTreeNode<E> prev = (AVLTreeNode<E>) grand.parent;

		parent.right = grand;
		grand.left = child;
		rotateCommon(prev, grand, parent, child);
	}

	/**
	 * 旋转的公共代码，do:
	 * 1.调整 prev 节点；
	 * 2.调整 child 节点；（这个其实木有）
	 * 3.需要重设置 父节点：parent,grand,child；
	 * 4.reset height:parent,prev
	 *
	 * @param prev   grand 的父节点	(may null)
	 * @param grand  失衡的节点
	 * @param parent 失衡的子节点
	 * @param child  失衡的孙子节点(may null)
	 */
	private void rotateCommon(AVLTreeNode<E> prev, AVLTreeNode<E> grand, AVLTreeNode<E> parent, AVLTreeNode<E> child) {
		//重新设置高度:child 高度不变；grand 虽然子树发生了变化，但是由于之前没有失衡 => child.height<=grand.childBefore.height!
		//错了，grand 节点忘记考虑挂着 parent 时候非 child 一端的高度了，由于不再挂，所以需要重新计算
		grand.resetHeight();
		parent.resetHeight();
		//parent.parent 无关 prev 是否为 null
		parent.parent = prev;
		if (prev != null) {
			if (grand.isLeftChild()) {
				prev.left = parent;
			} else {
				prev.right = parent;
			}
			//parent.parent = prev;
			prev.resetHeight();
		}
		grand.parent = parent;
		if (child != null) {
			child.parent = grand;
		}
	}

	@Override
	public Object string(Object node) {
		AVLTreeNode<E> myNode = (AVLTreeNode<E>) node;
		String parentString = "null";
		if (myNode.parent != null) {
			parentString = myNode.parent.element.toString();
		}
		return myNode.element + "_p(" + parentString + ")" + "_h(" + myNode.height + ")";
	}

	//endregion


}
